\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}


% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
\usepackage{ctex}%引入中文包
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{float}



\usepackage{listings}
\usepackage{xcolor}      %代码着色宏包
\usepackage{CJK}         %显示中文宏包

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{
 backgroundcolor=\color{lightgray}, 
 basicstyle = \footnotesize,       
 breakatwhitespace = false,        
 breaklines = true,                 
 captionpos = b,                    
 commentstyle = \color{mygreen}\bfseries,
 extendedchars = false,             
 frame =shadowbox, 
 framerule=0.5pt,
 keepspaces=true,
 keywordstyle=\color{blue}\bfseries, % keyword style
 language = C++,                     % the language of code
 otherkeywords={string}, 
 numbers=left, 
 numbersep=5pt,
 numberstyle=\tiny\color{mygray},
 rulecolor=\color{black},         
 showspaces=false,  
 showstringspaces=false, 
 showtabs=false,    
 stepnumber=1,         
 stringstyle=\color{mymauve},        % string literal style
 tabsize=2,          
 title=\lstname                      
}


% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{方丹吟 3190102758}
\chead{二叉树和节点的逻辑设计}
\rhead{2022.11.1}

\begin{center}
    \LARGE\songti\textbf{图的模板类设计} \\%标题
    \large\kaishu\textbf{方丹吟\qquad 3190102758}%一般是我的姓名
\end{center}


\section*{一、对数据结构的理解及设计思路}
\subsection*{1.图邻接矩阵}

\begin{itemize}
\item 图邻接矩阵类\textbf{AMGraph}中具有属性\textbf{NumVer}，用来表示图中的顶点数；属性\textbf{NumEdge}，用来表示图中边的数量；属性\textbf{vertex[]}，用来存放顶点的数据（名字）；属性\textbf{arc[][]}，用来存放边的信息；
\item 类AMGraph中的成员函数和实现的功能如下：
\begin{itemize}
\item[-] \textbf{AMGraph():}构造函数；\par
\item[-] \textbf{$ \sim $AMGraph():}析构函数；\par
\item[-] \textbf{listVertexes():}列出全部顶点；\par
\item[-] \textbf{listEdges():} 以 (u, v, w) 的方式列出全部边,  u, v是边的两端点节点, w 是权重；\par
\item[-] \textbf{Show():}打印邻接矩阵；\par
\item[-] \textbf{GetVertexI(char v):} 查找顶点v，找到返回顶点的下标，没找到返回-1; \par
\item[-] \textbf{InsertVertex(char v):} 插入一个顶点v；\par
\item[-] \textbf{DeleteVertex(char v):}删除一个顶点；\par
\item[-] \textbf{DeleteEdge(char v1,char v2):}删除顶点v1和v2之间的边；\par
\item[-] \textbf{InsertEdge(char v1,char v2, int w):} 插入一条由点v1和v2组成的边，v1->v2的权重分别为w\par

\end{itemize}

\end{itemize}
\subsection*{2.图邻接表}
\begin{itemize}
\item 邻接表类\textbf{ALGraph}中有属性\textbf{adjlist[]}，是由类\textbf{VertexNode}的实例构成的数组，用来存放顶点表中的结点；属性\textbf{vertexNum}，用来表示图中的顶点数；属性\textbf{arcNum}，用来表示图中边的数量；
\begin{itemize}
\item[-]类\textbf{VertexNode}是顶点结点，顶点结点包括属性\textbf{vertex}，存储顶点中的数据；属性\textbf{firstedge}，这是一个指向与顶点结点相邻的下一个ArcNode的指针；
\item[-]类\textbf{ArcNode}是边表结点，边表结点包括属性\textbf{adjvex}，存储这个边表节点在顶点结点表adjlist中的下标；属性\textbf{next}，这是一个指向相邻的下一个ArcNode的指针；属性\textbf{Weight}，存储顶点到该点边的权重
\end{itemize}

\item 类ALGraph中的成员函数和实现的功能如下：
\begin{itemize}
\item[-] \textbf{ALGraphLink():}构造函数；\par
\item[-] \textbf{$ \sim $ALGraphLink():}析构函数；\par
\item[-] 其余函数与类AMGraph中的成员函数功能相同
\end{itemize}

\end{itemize}

\section*{二、实现内容}
\begin{itemize}
\item 用户指定选用邻接表还是邻接矩阵表示实现图，如果使用邻接矩阵则输入1，使用邻接表则输入2；
\item 用户依次输入图的顶点数、顶点的编号（可以不按次序）、边的数量，并一次输入每一条边，输入结束后，根据用户的要求构建图邻接矩阵或图邻接表；
\item 使用函数 listVertexes(), 列出全部图中的全部节点；
\item 使用函数 listEdges(), 以 (u, v, w) 的方式列出全部边, 其中 u, v 是边的两端点节点, w 是权重
\item 使用函数 Show()打印邻接矩阵或邻接表；

\end{itemize}

\section*{三、函数代码}
\subsection*{1.邻接矩阵}
\begin{lstlisting}[caption={listVertexes()函数}]
void listVertexes() //输出每个顶点
    {
        cout<<"The Vertex of AMGraph are as follows: ";
        for (int i = 0; i < NumVertex; i++)
        {
            cout<<vertex[i]<<" ";
        }
        cout<<endl;

\end{lstlisting}

\begin{lstlisting}[caption={listEdges()函数}]
void listEdges()  //输出每一条边（u，v，w）
    {
        cout<<"The Edge of AMGraph are as follows: "<<endl;
        for (int i = 0; i < NumVertex; i++)
        {
            for(int j = 0 ; j < NumVertex ; j++)
            {
                if(arc[i][j] != 0)
				    cout<<"("<<vertex[i]<<","<<vertex[j]<<","<<arc[i][j]<<")  ";
			}
            
        }
        cout<<endl;
\end{lstlisting}

\begin{lstlisting}[caption={Show()函数}]
void Show() //输出邻接矩阵
    {
        cout<<"The Adjacent Matrix Graph is as follows:"<<endl;
        int i,j;
        cout<<"      ";
        for (i = 0; i < NumVertex; i++)
        {
            cout<<vertex[i]<<"     ";
        }
        cout<<endl;
        for (i = 0; i < NumVertex; i++)
        {
            cout<<vertex[i]<<"     ";
            for (j = 0; j < NumVertex; j++)
                cout<<arc[i][j]<<"     ";
            cout<<endl;
        }
    }
\end{lstlisting}

\subsection*{2.邻接表}

\begin{lstlisting}[caption={listVertexes()函数}]
template<class DT>
void ALGraph<DT>::listVertexes()
{
    cout<<"The Vertex of Graph are as follows: ";
    for (int i = 0; i < vertexNum; i++)
    	cout<<adjlist[i].vertex<<" ";
    cout<<endl;
\end{lstlisting}

\begin{lstlisting}[caption={listEdges()函数}]
template<class DT>
void ALGraph<DT>::listEdges()
{
    cout<<"The Edge of Graph are as follows: "<<endl;
    for (int i = 0; i < vertexNum; i++)
    {
        if (adjlist[i].firstedge != NULL)
        {
            ArcNode *p = adjlist[i].firstedge;
            while (p != NULL)
            {
            cout<<"("<<adjlist[i].vertex<<",";
            DT j = p->adjvex;
            int q = VertexIndex(j);
            cout<<adjlist[q].vertex<<","<<p->Weight<<") ";
            p = p->next;
            }
        }   
    }    
    cout<<endl;
}
\end{lstlisting}

\begin{lstlisting}[caption={Show()函数}]
template<class DT>
void ALGraph<DT>::Show()
{
    cout<<"The Adjacent List Graph is as follows:"<<endl;
    for (int i=0;i<vertexNum;i++)
    {
        cout<<adjlist[i].vertex;
        ArcNode *p = adjlist[i].firstedge;
        while(p)
        {
            cout<<"-("<<p->Weight<<")->";
            cout<<p->adjvex;
            p = p->next;
        }
        cout<<"->NULL"<<endl;
    }
}
\end{lstlisting}


\section*{四、测试结果}
\begin{figure}[H]
    \centering
     \includegraphics{AMGraph}
     \caption{邻接矩阵测试结果}
\end{figure}

\begin{figure}[H]
    \centering
     \includegraphics{ALGraph}
     \caption{邻接表测试结果}
\end{figure}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
